import java.util.Comparator;
import java.util.PriorityQueue;
class IntComper implements Comparator<Integer> {
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2 - o1;
    }
}
public class TOP_K {
    //前最大k个数
    //做法一：把数组排序取出前看个最大，不过如果数据量非常大，你无法在内存中排序
    //做法二：把所有数据放到优先级队列，出队k次，不过如果数据量非常大，你无法将所有数据放到优先级队列中
    //做法三：
    //建小根堆，先选出数组前k个数据，在把剩下的元素比较
    //如果比堆顶大，则堆顶出队(因为是小根堆，堆顶最小)，然后把当前数组元素入队

    public int[] maxlestk(int[] arr,int k){
        int[] ret = new int[k];
        PriorityQueue<Integer> priorityQueue= new PriorityQueue<>();
        for (int i = 0; i < k; i++) {
            priorityQueue.offer(arr[i]);
        }
        for (int i = k; i < arr.length; i++) {
            int tmp = priorityQueue.peek();
            if(arr[i] > tmp){
                //i下表元素如果大于堆顶元素，那么说明堆顶元素一定不是前看个最大元素之一
                priorityQueue.poll();
                priorityQueue.offer(arr[i]);
            }
        }
        for (int i = 0; i < k ; i++) {
            ret[i] = priorityQueue.poll();
        }
        return ret;
    }
    //前最小k个数
    public int[] smallestk(int[] arr,int k){
        int[] ret = new int[k];
        PriorityQueue<Integer> priorityQueue= new PriorityQueue<>(new IntComper());
        for (int i = 0; i < k; i++) {
            priorityQueue.offer(arr[i]);
        }
        for (int i = k; i < arr.length; i++) {
            int tmp = priorityQueue.peek();
            if(arr[i] < tmp){
                //i下表元素如果大于堆顶元素，那么说明堆顶元素一定不是前看个最大元素之一
                priorityQueue.poll();
                priorityQueue.offer(arr[i]);
            }
        }
        for (int i = 0; i < k ; i++) {
            ret[i] = priorityQueue.poll();
        }
        return ret;
    }
}
